#include "header/BTree.h"
#include <stdio.h>
#include <stdlib.h>

/**
 * @brief 返回关键字k的大致位序(p->key[i-1]<k<=p->key[i])
 * 
 * @param t BTree
 * @param k 关键字
 * @return int (p->key[i-1]<k<=p->key[i])
 */
int search(BTree t, KeyType k){
    int i = 1;
    // 关键字范围内查找
    while(i <= t->keynum && t->key[i] < k){
        i++;
    }
    return i;
}

/**
 * @brief 分裂结点，前一半留在原结点，后一半移入ap指向的结点
 * 
 * @param t     BTree
 * @param s     mid index
 * @param ap    targe BTree
 * @param rec   record data
 */
void split(BTree t, int s, BTree *ap, void *rec){
    int i, j, n = t->keynum;
    // 生成新结点
    (*ap) = getBTree();
    // 改变孩子指针数组指向
    (*ap)->ptr[0] = t->ptr[s];
    // 将结点后一半移向ap所指向的结点
    for (i = s + 1, j = 1; i <= n; i++, j++){
        (*ap)->key[j] = t->key[i];
        (*ap)->record[j] = t->record[i];
        (*ap)->ptr[j] = t->ptr[i];
    }
    (*ap)->parent = t->parent;
    (*ap)->keynum = n - s;
    for (i = 0; i <= n - s; i++){
        // 修改子结点的双亲指针指向
        if ((*ap)->ptr[i]){
            (*ap)->ptr[i]->parent = *ap;
        }
    }
    // 前一半保留
    t->keynum = s - 1;
}

/**
 * @brief 
 * 
 * @param a         
 * @param last      
 * @return array 
 */
array append(array a, int last){
    // 如果满了则扩容
    if (a->n == a->max){
        a->thelast = (int *)realloc(a->thelast, sizeof(int) * ((a->max) + 10));
    }
    a->max += 10;
    a->thelast[(a->n)++] = last;
    return a;
}

/**
 * @brief Get the Array object
 * 
 * @return array 
 */
array getArray(){
    array a = (array)malloc(sizeof(struct arr));
    a->max = 10;
    a->n = 0;
    a->thelast = (int *)malloc(sizeof(int) * (a->max));
    return a;
}

/**
 * @brief 
 * 
 * @param t BTree
 * @param k 待查关键字
 * @return resultptr 结果信息指针
 */
resultptr searchBTree(BTree t, int k){
    // p-指向待查结点 q-指向双亲
    BTree p = t, q = NULL;
    if(t == NULL){
        return NULL;
    }
    // isFound-记录是否找到结点, i-结点关键字大致位序
    int isFound = 0, i = 0;
    while (p != NULL && isFound == 0){
        // 结点关键字大致位序
        i = search(p, k);
        if (i <= p->keynum && p->key[i] == k){
            // 找到待查关键字
            isFound = 1;
        } else {
            // 指针下移
            q = p;
            // 从0开始
            p = p->ptr[i-1];
        }
    }
    if (isFound){
        return getResult(p, i, 1);
    } else {
        return getResult(q, i, 0);
    }
}

/**
 * @brief 创建新结点
 * 
 * @param p     new BTNode
 * @param left  the left part
 * @param x     关键字
 * @param right the right part
 * @param rec   record data
 */
void newRoot(BTree *p, BTree left, KeyType x, BTree right, void *rec){
    (*p) = getBTree();
    (*p)->keynum = 1;
    (*p)->key[1] = x;
    (*p)->record[1] = rec;
    (*p)->ptr[0] = left;
    (*p)->ptr[1] = right;
    // 如果左边部分需要接入新结点
    if(left){
        left->parent = *p;
    }
    // 如果右边部分需要接入新结点
    if(right){
        right->parent = *p;
    }
    // 双亲结点置空
    (*p)->parent = NULL;
}

/**
 * @brief 插入结点, 将关键字x和新结点指针ap分别插入t->key[i], q->ptr[i]
 * 
 * @param t   待插入结点
 * @param i   插入的位序(i-1 < position <= i)
 * @param x   关键字
 * @param p   新结点指针
 * @param rec record data
 */
void insert(BTree t, int i, KeyType x, BTree p, void *rec){
    int j, n = t->keynum;
    // 右移为新结点腾出空间
    for (j = n; j >= i; j--){
        t->ptr[j + 1] = t->ptr[j];
        t->key[j + 1] = t->key[j];
        t->record[j + 1] = t->record[j];
    }
    t->ptr[i] = p;
    t->key[i] = x;
    t->record[i] = rec;
    if (p){
        p->parent = t;
    }
    t->keynum++;
}

/**
 * @brief 插入, 将关键字k插入t树的q结点的第i-1~i之间
 * 
 * @param t         BTree
 * @param k         关键字
 * @param q         插入的目标结点
 * @param i         关键字插入位序
 * @param rec       record data
 * @return Status 成功返回SUCCESS 否则返回ERROR
 */
Status insertBTree(BTree *t, KeyType k, BTree q, int i, void *rec){
    // s-中位数, finished-是否完成插入操作, need-是否需要改变根结点
    int s, finished = 0, need = 0;
    // x-关键字
    KeyType x;
    // 新结点指针
    BTree ap;
    void *recd;
    // 目标结点指向若空则置新
    if (q == NULL){
        newRoot(t, NULL, k, NULL, rec);
    }else{
        x = k;
        ap = NULL;
        recd = rec;
        while (need == 0 && finished == 0){
            insert(q, i, x, ap, recd);
            if (q->keynum < M){
                // 关键字个数未超出M，标记完成插入操作
                finished = 1;
            }else{
                // 关键字总数达到M，需要分裂结点
                s = (M + 1) / 2;
                split(q, s, &ap, recd);
                // 中位数位序的关键字, 下一个循环插入到双亲结点中
                x = q->key[s];
                recd = q->record[s];
                if (q->parent){
                    // 未分裂到根节点, 向上检查关键字总数是否超出M
                    q = q->parent;
                    i = search(q, x);
                }else{
                    // 分裂到根节点，需要产生新的根节点
                    need = 1;
                }
            }
        }
        // 产生新的根节点
        if (need){
            newRoot(t, q, x, ap, recd);
        }
    }
    return SUCCESS;
}

/**
 * @brief 找出Ai子树最下层非终端结点的最小关键字代替Ki
 * 
 * @param t 
 * @param i 
 */
void successor(BTree *t, int i){
    if((*t) == NULL){
        return;
    }
    BTree temp = (*t)->ptr[i];
    // 下移至最下层
    while (temp->ptr[0]){
        temp = temp->ptr[0];
    }
    // 替换Ki
    (*t)->key[i] = temp->key[1];
    (*t)->record[i] = temp->record[1];
    // t转为最下层结点返回
    (*t) = temp;
}

/**
 * @brief 从结点中删除关键字key[i]
 * 
 * @param t 目标节点
 * @param i 关键字位序 
 */
void removeKey(BTree t, int i){
    // 左移关键字覆盖
    while (i < t->keynum){
        t->key[i] = t->key[i + 1];
        t->record[i] = t->record[i + 1];
        t->ptr[i] = t->ptr[i + 1];
        i++;
    }
    t->keynum--;
}

/**
 * @brief 调整BTree
 * 
 * @param root 根节点
 * @param t    目标节点
 * @param i    当前节点在双亲的位序
 */
void restore(BTree *root, BTree *t, int i){
    // 目标节点的双亲结点
    BTree par = (*t)->parent;
    if (par == NULL){
        // 若为根节点
        if(par == NULL){
            if((*t)->keynum == 0){
                (*root) = (*t);
                (*root)->parent = NULL;
                // free(*t);
            }
        }
        return;
    }
    // 目标节点在双亲结点的位序
    int j = 0;
    while (par->ptr[j] != (*t)){
        j++;
    }
    if (j > 0 && par->ptr[j - 1]->keynum > (M - 1) / 2){
        // 左兄弟结点个数足够
        // 目标节点的左兄弟结点
        BTree sib = par->ptr[j - 1];
        (*t)->keynum++;
        int n = (*t)->keynum;
        int k;
        // 目标节点的关键字右移，为调整所得的新节点腾出空间
        for (k = n; k > 0; k--){
            (*t)->key[k] = (*t)->key[k - 1];
            (*t)->record[k] = (*t)->record[k - 1];
            (*t)->ptr[k] = (*t)->ptr[k - 1];
        }
        (*t)->ptr[1] = (*t)->ptr[0];
        (*t)->ptr[0] = sib->ptr[sib->keynum];
        if((*t)->ptr[0] != NULL){
            (*t)->ptr[0]->parent = (*t);
        }
        // 将大于该关键字的关键字下移
        (*t)->key[1] = par->key[j];
        (*t)->record[1] = par->record[j];
        // 将左兄弟结点中最大的关键字上移至双亲结点
        par->key[j] = sib->key[sib->keynum];
        par->record[j] = sib->record[sib->keynum];
        // 删除左兄弟结点中的最大关键字
        removeKey(sib, sib->keynum);
    } else if (j >= 0 && par->keynum >= j + 1 && par->ptr[j + 1]->keynum > (M - 1) / 2){
        // 右兄弟结点个数足够
        BTree sib = par->ptr[j + 1];
        (*t)->keynum++;
        // 直接把双亲结点的右一个关键字放入目标节点的最大位
        (*t)->key[(*t)->keynum] = par->key[j + 1];
        (*t)->record[(*t)->keynum] = par->record[j + 1];
        (*t)->ptr[(*t)->keynum] = sib->ptr[0];
        if((*t)->ptr[(*t)->keynum] != NULL){
            (*t)->ptr[(*t)->keynum]->parent = (*t);
        }
        // 右兄弟结点最小的上移
        par->key[j + 1] = sib->key[1];
        par->record[j + 1] = sib->record[1];
        // 删除右兄弟结点的最小关键字(实际上是覆盖了位序为1的关键字, 因为左移后为0而0未使用)
        removeKey(sib, 0);
    } else {
        // 左右兄弟结点都不够
        if (j != 0){
            // 目标节点是位于右边的结点
            // 目标节点的左兄弟节点
            BTree sib = par->ptr[j - 1];
            ++sib->keynum;
            // 双亲结点中分割目标节点和左兄弟结点的关键字下移至左兄弟结点
            sib->key[sib->keynum] = par->key[j];
            sib->record[sib->keynum] = par->record[j];
            sib->ptr[sib->keynum] = (*t)->ptr[0];
            par->keynum--;
            // 循环变量
            int k;
            // 双亲结点的关键字左移
            for (k = j; k < par->keynum; k++){
                par->key[k] = par->key[k + 1];
                par->record[k] = par->record[k + 1];
                par->ptr[k] = par->ptr[k + 1];
            }
            // 将目标节点的剩余信息合并到左兄弟结点中
            for (k = 1; k <= (*t)->keynum; k++){
                sib->keynum++;
                sib->key[sib->keynum] = (*t)->key[k];
                sib->record[sib->keynum] = (*t)->record[k];
                sib->ptr[sib->keynum] = (*t)->ptr[k]; 
            }
            // free(*t);
            (*t) = sib;
            for (int i = 0; i <= sib->keynum;i++){
                if(sib->ptr[i]){
                    sib->ptr[i]->parent = sib;
                }
            }
        } else if (j != M){
            // 目标节点是位于左边的结点
            // 目标节点的右兄弟节点
            BTree sib = par->ptr[j + 1];
            int count = (*t)->keynum + 1;
            par->keynum--;
            sib->keynum += count;
            // 循环变量
            int k;
            // 右兄弟结点关键字右移
            for (k = sib->keynum; k > count; k--){
                sib->key[k] = sib->key[k - count];
                sib->record[k] = sib->record[k - count];
                sib->ptr[k] = sib->ptr[k - count];
            }
            // 双亲结点关键字下移到右兄弟结点
            sib->ptr[count] = sib->ptr[0];
            sib->key[count] = par->key[j + 1];
            sib->record[count] = par->record[j + 1];
            // 双亲结点指向子节点的指针左移
            par->ptr[j] = par->ptr[j + 1];
            // 双亲结点关键字左移
            for (k = j + 1; k <= par->keynum; k++){
                par->key[k] = par->key[k + 1];
                par->record[k] = par->record[k + 1];
                par->ptr[k] = par->ptr[k + 1];
            }
            // // 目标节点的剩余信息并入右兄弟结点
            for (k = 1; k <= (*t)->keynum; k++){
                sib->key[k] = (*t)->key[k];
                sib->record[k] = (*t)->record[k];
                sib->ptr[k] = (*t)->ptr[k];
            }
            sib->ptr[0] = (*t)->ptr[0];
            // free(*t);
            (*t) = sib;
            for (int i = 0; i <= sib->keynum;i++){
                if(sib->ptr[i]){
                    sib->ptr[i]->parent = sib;
                }
            }
        }
        (*t) = (*t)->parent;
        if((*t) == (*root) && (*root)->keynum == 0){
            (*root) = (*root)->ptr[0];
            (*root)->parent = NULL;
            free(*t);
        }
    }
    // 如果双亲结点也如此，以双亲结点为目标节点调整树
    if (par->keynum < (M - 1) / 2){
        restore(root, &par, j);
    }
}

/**
 * @brief 删除，删除B树root上t结点的第i个关键字
 * 
 * @param root  根节点
 * @param t     目标节点
 * @param i     删除关键字位序
 */
void deleteBTree(BTree *root, BTree *t, int i){
    // 不是最下层的非终端节点
    if((*t)->ptr[i]){
        // 找出Ai子树最下层非终端结点的最小关键字代替Ki, t已转为最下层结点
        successor(t, i);
        // 删除最下层非终端节点中的最小关键字
        deleteBTree(root, t, 1);
    } else {
        // 是最下层非终端节点
        removeKey((*t), i);
        if((*t)->keynum < (M - 1) / 2){
            restore(root, t, i);
        }
    }
}

/**
 * @brief 销毁BTree
 * 
 * @param t         BTree
 * @return Status 
 */
Status destroyBTree(BTree t){
    if(t == NULL){
        return ERROR;
    }
    int i = 0;
    for (i = 0; i <= t->keynum;i++){
        if(t->ptr[i]){
            // 递归销毁
            destroyBTree(t->ptr[i]);
        }
    }
    free(t);
    return SUCCESS;
}

/**
 * @brief 打印BTree索引结构
 * 
 * @param t     BTree
 */
void printBTree(BTree t){
    if (t == NULL){
        return;
    }
    array last = getArray();
    print(t, 1, last);
}

/**
 * @brief 将层数返回一层
 * 
 * @param a 
 * @return array 
 */
array pop(array a){
    if (a == NULL || a->n == 0){
        return a;
    }
    a->n -= 1;
    return a;
}

/**
 * @brief 打印索引结构如下所示
|
|------>|
|       |------>|
|       |       |->1
|       |->2
|       |------>|
|               |->3
|->4
|------>|
        |------>|
        |       |->5
        |->6
        |------>|
        |       |->7
        |->8
        |------>|
                |->9
                |->10
 * 
 * @param t     BTree
 * @param depth 打印的深度
 * @param last  存放关键字位序的数组
 */
void print(BTree t, int depth, array last){
    int i, j;
    if(t == NULL){
        return;
    }
    // 第一个|
    printf("|\n");
    for (i = 0; i <= t->keynum;i++){
        // 打印最下层结点关键字
        if(i != 0 && (t->key[i] != -1)){
            for (j = 0; j < depth - 1; j++){
                if(!(last->thelast[j])){
                    printf("|");
                } else {
                    printf(" ");
                }
                printf("\t");
            }
            printf("|->");
            printf("%d\n", t->key[i]);
        }
        if((t->ptr[i]) != NULL){
            for (j = 0; j < depth - 1;j++){
                if(!(last->thelast[j])){
                    printf("|");
                } else {
                    printf(" ");
                }
                printf("\t");
            }
            printf("|------>");
            if(i == t->keynum){
                append(last, 1);
            } else {
                append(last, 0);
            }
            print(t->ptr[i], depth + 1, last);
            pop(last);
        }
    }
}

/**
 * @brief 初始化BTree结点
 * 
 * @return BTree BTree结点
 */
BTree getBTree(){
    BTree t = (BTree)malloc(sizeof(BTNode));
    if(t == NULL){
        return NULL;
    }
    t->parent = NULL;
    t->keynum = 0;
    for (int i = 0; i <= M;i++){
        t->ptr[i] = NULL;
        t->key[i] = -1;
        t->record[i] = NULL;
    }
    return t;
}

/**
 * @brief Get the Result object
 * 
 * @param t     指向找到的结点
 * @param index 结点位序
 * @param tag   是否找到，1：查找成功 0：查找失败
 * @return resultptr 
 */
resultptr getResult(BTree t, int index, int tag){
    resultptr result = (resultptr)malloc(sizeof(struct result));
    result->pt = t;
    result->i = index;
    result->tag = tag;
    return result;
}
